1. Field of the Invention
The present system and method relates to secure communications, system security and cryptography. A particular emphasis is placed on has cryptographic solutions based upon Public Key Infrastructure (Pki) based methods.
2. Description of Related Art
In order to communicate securely over an insecure communication channel one needs to encrypt messages. Such encryption schemes fall into two broad classes—private key schemes and public key schemes. In a private key encryption scheme the Sender and the Receiver share a secret key K. This key is used both to encrypt and to decrypt the message. In a public key encryption scheme the Receiver has a pair of related keys—a secret key and a public key. He reveals his public key to everyone. To send a message to Receiver, the Sender encrypts it using Receiver's public key. Under certain assumptions (explained below), only the holder of the secret key, i.e., Receiver, can decrypt the message using a feasible computation.
When using a private key encryption scheme it is necessary for each pair of communicating parties to agree on a shared secret key before encrypted communication begins. In settings where the parties know each other and expect to communicate in the future this can be established quite easily. For example, such a setting might work for a communication network within a company where the messages are sent between the employees of the company. All the employees know each other in the sense that they are all listed in the company pay-roll. Each employee can establish private keys when joining the company. In contrast, a setting where private key encryption may not be appropriate is a setting similar to the Internet where the parties do not have a way to get to know each other. In such settings, public key schemes offer immense practical advantages over private key schemes (with possibly only one novel exception, which is below described). In public key encryption each user simply has to publish his public key and keep his private key secret. No prior agreement is needed between the parties. Such considerations account for the enormous popularity of public key encryption schemes such as RSA over private key schemes.
However, from the standpoint of security, a particular private key encryption scheme called the one-time pad is the gold standard. In the one-time pad scheme, a secret key is a string of random bits and encryption is done by computing the exclusive-or of successive bits of the message with successive bits of the key. Decryption is done by computing the exclusive or of the bits of the cipher-text with the bits of the secret key. One-time pad schemes have the strongest possible security. As long as the secret key is not compromised, an eavesdropper who gets the cipher-text has no information that picks out the particular message transmitted over any other message. This is true even if one allows the attacker to have unlimited computational resources. Such a level of security is called perfect security or information-theoretic security and refers to the fact that it is the absence of information (about the message in the cipher-text) and not the computational prowess of the attacker that limits her. As the name implies, the key in a one-time pad is meant to be used just once and the key must have as many bits as the message transmitted. This is well suited for applications where the users know in advance the approximate size and number of messages they plan to exchange in a give time. In such applications the users are able to determine the appropriate size of the secret key they need to share before communication begins. On the other hand, in applications where the size of the key cannot be determined ahead of time, using the one time pad scheme would require either exchanging a very large key with the possibility of never using much of it, or exchanging a shorter key with the possibility of ending the encrypted communication before the entire message got transmitted. Therefore, for these applications public-key schemes might be more appropriate.
Unfortunately, there are no perfectly secure public-key schemes. Public-key schemes are not secure if the attacker is given unlimited computational resources. An attacker can simply run through all possible secret keys, see which one is related to the public-key, and then use this secret key to decrypt the message. To obtain a public-key scheme one makes a computational assumption—that decryption is difficult for an attacker who can only perform probabilistic polynomial time computation. For example, in order to show that the RSA public key encryption scheme is secure, one needs to assume that factoring large integers is hard. (In fact, this assumption is necessary but not sufficient to ensure the security of RSA.) Thus, while public-key encryption offers logistic advantages, schemes based on this idea are vulnerable if the attacker has enormous resources at her disposal or the underlying assumption about the hardness of some computational problem turns out to be false. It has been shown that on a quantum computer the factoring problem can be solved efficiently. Thus, the security of RSA rests on our inability to build quantum computers—not a satisfactory state of affairs for long-term, high-security communication.
A second drawback of public-key encryption is the computational cost of the encryption and decryption operations. Schemes such as RSA use large moduli (typically at least 500-bit) and have to compute expensive operations such as exponentiation with respect to such moduli. In contrast, a one-time pad uses the very fast operation of bitwise exclusive-or.
To summarize, the one-time pad private-key encryption scheme achieves the best security possible and essentially the fastest possible computation—bitwise exclusive-or. As mentioned above it is most appropriate for applications when the Sender and Receiver are able to to establish a private-key. The one-time pad scheme can also be extended to scenarios where there are many pairs of senders and receivers. In such a scenario, each pair of Sender and Receiver shares its own private key. This means that each Receiver must keep as many keys as there are parties that send messages to it which can become rather costly.
Therefore, when the one-time pad scheme is extended to applications where there are many parties it does not scale well.